Heaps
=====

We are looking for an efficient implementation of priority queues.
Recall that priority queues support the access and deletion of the 
minimum item with findMin and deleteMin, repsectively.

Option 1: Use a linked list
	- Insertion at front is O(1)
	- Finding/deleting Min is O(N)

Option 2: Keep list sorted
	- Finding/deleting Min is O(1)
	- Insertion is O(N)

Option 3: Use a Binary-search Tree
	- All operations are O(logN) on average
	- However, input is typically not sufficiently random, which
	  leads to imbalance and loss of efficiency

Option 4: Keep the tree balanced
	- Too expensive in general

Here, we describe an implementation of priority queues such that:
	- Use a simple array
	- Insert and deleteMin are O(logN) in the worst case
	- Insert is O(1) on average
	- findMin is O(1) in the worst case


Partially-ordered Tree
----------------------

What is a Partially-ordered Tree (POT)?
	A complete binary tree that obeys the POT property

What is a Complete Binary Tree?
	All levels except the bottom are completely filled
	Nodes at the bottom level are as far left as possible

What is the height of a complete binary tree?
	A tree with N nodes has height at most logN

What is the POT order property?
	For every node X, the value of X's parent is <= the value of X
	The root has the smallest value

How do we Insert into a POT?
	Add an item at the next available location
	Percolate up until the order is correct
		Compare an item with its parent
		Swap if the parent is larger

Class exercise
	Show the result of inserting 5, 2, 8, 3, 1, 9, 6, 4 into a POT
	Show the result of inserting E, C, H, A, G, D, F, B into a POT

What is the Big-Oh of Insert?
	O(log N) in the worst case
	O(1) in the average case (percolation terminates early: 2.6)

How do we DeleteMin from a POT?
	Replace the root with the last item
	Percolate down until the order is correct
		Compare an item with its smaller child
		Swap if the parent is larger

Class exercise
	Show the result of DeleteMin from the first of the previous POT

What is the Big-Oh of DeleteMin?
	O(log N) in the worst case
	O(log N) in the average case


Binary Heap
-----------

What is a Binary Heap?
	An implementation of a POT using an array

How do we store a complete binary tree in an array?
	Store the nodes in level order
	The root is at A[1] (A[0] not used, implicitly -inf)
	The children of the root are at A[2] and A[3]
	In general:
		The left child of the node at A[i] is at A[2i]
		The right child of the node at A[i] is at A[2i+1]
	The parent of the node at A[i] is at A[i/2]

Where is the next insertion point?
	If currentSize is the number of elements currently stored in the
          heap, the next insertion point is at A[currentSize + 1]

Let us now take a look at the code for the basic operations

    // default constructor
    // note that we may have to increase the size of the array as we
    // did in our earlier implementation of lists with arrays. We ignore
    // this in the following code fragments.

    public BinaryHeap() {
        currentSize = 0;
        array = new Comparable[DEFAULT_CAPACITY];
    }


    // findMin
    // note that in a heap the minimum is the "root" of the tree

    public Comparable findMin() {
        if (isEmpty())
            throw new UnderflowException("Empty binary heap");
        return array[1];
    }


    // insert
    // stick at the next available position and percolate up
    // set array[0] to x for the first couple of insertions

    void insert( Comparable x ) {
        int hole = ++currentSize;
        array[ 0 ] = x;
        for( ; x.compareTo( array[ hole / 2 ] ) < 0; hole /= 2 )
            array[ hole ] = array[ hole / 2 ];
        array[ hole ] = x;
    }

    
    // deleteMin
    // findMin (root of the tree), place last inserted item in root and
    // percolate down through smaller children

    public Comparable deleteMin( ) {
        Comparable minItem = findMin( );
        array[ 1 ] = array[ currentSize-- ];
        percolateDown( 1 );
        return minItem;
    }

    private void percolateDown( int hole ) {
        int child;
        Comparable tmp = array[ hole ];
        for( ; hole * 2 <= currentSize; hole = child ) {
            child = hole * 2;
            if( child != currentSize &&
                    array[ child + 1 ].compareTo( array[ child ] ) < 0 )
                child++;
            if( array[ child ].compareTo( tmp ) < 0 )
                array[ hole ] = array[ child ];
            else
                break;
        }
        array[ hole ] = tmp;
    }


Building a Heap
---------------

How long does it take to build a heap with N items?
	Repeat insert N times => O(N log N)

Can we do better?
	Yes
        A heap of N items can be built in O(N) time

Given a complete binary tree with N items in arbitrary order (or given an
array of N items in arbitrary order), what must be done to produce a heap
with the order property?
	Percolate-down each item

Which positions on the tree do not need to be percolated down?
	The leaf nodes in the tree can not move down

Which nodes in the tree should be percolated down first/last?
	Percolate down in reverse level order
	When percolateDown is called on node i, the descendants of node i
	  have already been processed

Class exercise
	Show the result of buildHeap on 5, 2, 8, 3, 1, 9, 6, 4
	Show the result of buildHeap on E, C, H, A, G, D, F, B

Here is the code for buildHeap

    private void buildHeap() {
        for(int i = currentSize / 2; i > 0; i--)
            percolateDown(i);
    }

How can we show that buildHeap is indeed O(N)?
	The sum of node-heights is a bound on the percolate steps
	Consider a perfect binary tree of height H containing N nodes
	Mark edges as follows:
		For each node (other than leaf nodes): Mark one left edge,
		  then all right edges
	With this procedure, each edge is marked exactly once, except for
		the edges along the rightmost path from the root node
	The tree has N-1 edges and the rightmost path H edges
	Consequently, the number of darkened edges, i.e., the sum of node
	  heights, is N - H - 1


HeapSort
--------

How can we use a Priority Queue to sort a list of items?
	For each item x: insert x into PQ
	while PQ not empty: deleteMin gives next item in sorted order

What is the running time of this algorithm?
	O(N log N)

How much space is used by this algorithm?
	N for the list
	another N for the PQ

Describe a similar algorithm that sorts in-place using only a single
array of N items
	Call buildHeap on the array of N items
	Repeat N-1 times
		Swap the first item (root) with the last item
		Decrement the heap size
		percolateDown the first item

What is the order of the items in the resulting array?
	A Min Heap gives the items in decreasing order

How can we change the algorithm to give increasing order?
	A Max Heap gives the items in increasing order

Class exercise
	Show the result of heapsort on E, C, H, A, G, D, F, B

Here is the code for Heap Sort

	void heapsort(Comparable[] array) {
	    for (int i = array.length/2; i >= 0; i--)
	        percolateDown(array, i, array.length);
	    for (int j = array.length-1; i > 0; i--) {
	        swap(array, 0, j);
		percolateDown(array, 0, j);
	    }
	}

How can a heap work with indices starting at 0?
	The parent of the node at i is at (i-1)/2
	The left child of the node at i is at 2i+1
	The right child of the node at i is at 2i+2